CS432

Assignment 1: Buffer Manager

Deadline: September 20, 23:59PM. No late submissions are permitted. Check this page frequently for any updates or clarifications. This is a group project: You have to perform this project in groups of two students.

Frequently asked questions (last updated 9/14/2001)

Introduction

Read first the whole assignment carefully before you start implementing and before you start creating projects and workspaces. There are links to more instructions at the end of this text.

In this assignment you will implement a buffer manager. The buffer manager is responsible for bringing pages from the disk to the main memory as needed. The buffer manager:

Flushes a page to the disk, if required
Pins a page to the buffer, bringing a page from the disk, if necessary
Unpins a page in the buffer by reducing the pin counter for that page
Frees up space that is allocated to a given page on the disk.
Allocates one or more frames and brings the requested pages from the disk
Keeps track of statistics of operations on buffer pool

In addition, you will be required to run experiments studying the effect the size of the buffer pool has on performance and present your results.

Description and Specifications

You will be given the code that implements a database class (DB) and a page class (Page). The definition of public interface for the buffer manager class (BufMgr) is available, but is not implemented. You can find out more about the implemented classes and types here :

Also, you'll be given a visualization tool, BufferSim, which simulates buffer manager operations.

The source code for the project is located in the directory \\goose\courses\cs432-fall01\A1. The directory contains three subdirectories: code, examples, and globaldefs.

Directory "code":

bufmgr.cpp -- the code skeleton for the Buffer Manager, where you will find the detailed specs of the methods that you need to implement as well as the necessary interfaces.
bufmgr.h - the definition for the class BufMgr.
test.cpp, bmtest.cpp, test.h, bmtest.h-- the source codes for the test that the Buffer Manager needs to pass. RunTests runs the tests on the Buffer Manager.
main.cpp - the main routine that initializes the Minibase, including the buffer manager, and run the test.
db.cpp, db.h, page.cpp, page.h - files that implement the DB class and Page classes. You should compile both page.cpp and db.cpp and link it with your programs.
da_types.h, new_error.h, minirel.h, system_defs.h - the header files for Minibase which define various types, global variables, etc.

Directory globaldefs:

globaldefs\*.[Ch] - files to make a static library (Win32, Debug) "globaldefs.lib" that defines the global variables in Minibase. You should link the library with your buffer manager project. Details on how to create the static library are here.

Directory example:

BufferSim.exe - a visualization tool that simulates buffer manager operations.
proj1.exe - a sample executable (Win32, Console Application) which demonstrates the working of a buffer manager.

You are required to modify and fill in the gaps in bufmgr.cpp and bufmgr.h, specifically :

You need to implement the methods listed in bufmgr.cpp based on specifications as described in bufmgr.cpp. You do not need to modify any other files. However if you do decide to look at them you will learn more about how the project works. You are free to add any private methods or members into BufMgr, or make a function inline if you want to.
Your buffer manager should implement the Clock and MRU replacement policies, which are described in the textbook. (Hint : A good way to make your buffer manager extensible is to define the interface for a base replacement policy class with virtual functions etc. Then derive the Clock replacement policy from it, and implement the virtual functions. This way minimum changes are required if the buffer manger switches to a different replacement policy such as the MRU policy that you will need to implement as well.)
In order to work with BufferSim, your buffer manager must write out a file in the format described in the documentation of the BufferSim. Check the above link for details and examples.
Your buffer manager should collect the following statistics:

1) Number of PinPage requests made.
2) Number of PinPage requests that result in a miss (i.e. the page is not in the buffer when the pin request is made)
3) Number of "dirty" pages written to disk.
4) Total time taken to run the test. (This will be collected for you by the code that already exists in main.cpp)

Also you will need to write two functions (ResetStat() and PrintStat()): one to reset the statistics and one to report the statistics using standard input/output stream libraries.
You need to link your implementation with the rest of the files, and make sure that the tests run successfully. (i.e. your output should look like the output from proj1.exe).

Presenting Statistical Data:

For each of the replacement policy you implemented (MRU and Clock), you need to do the following:

       1) After your tests have run successfully, you will need to run five experiments while varying the buffer size, and describe the effects a larger buffer pool has on the statistics (including time) that you have collected. You should also explain these variations.
        2) Running the experiments is basically running the tests provided for you again with different buffer sizes. At this point you should also look at the test procedures and see why the buffer size increases will affect the performance. (note: we are only interested in statistics relating to the fourth and fifth tests.)
        3) In order to change the buffer size go to the file minirel.h and change the value of the constant NUMBUF. The buffer sizes recommended are 50,100,150,200, and 250. (Note: The project you submit should have buffer size 50 only. We don't want five copies of everybody's project.)
        4) Remember to close all major applications on your computer before running the tests, since they will affect the time it takes to run the tests.

In addition, you should then contrast the performance of the buffer manager when using the replacement policies that you have implemented. Remember that if you define the replacement policy as a base class with virtual functions then all you have to do is derive the MRU and Clock classes and implement the functions.

Coding Conventions

You need to follow certain coding convention for all your assignments.

Names for all classes/method/type should start with a capital letter. Break multiple words with capital letters. For example AddFileEntry.
Names for all members/variables should start with small letters. Break multiple words with capital letters. For example numOfPages;
Names for all enum/macro should be all capital letters. Break multiple words with underscore. For example MINIBASE_DB.
Follow the coding convention in the BufMgr class. If you create a new function, make sure the header contains the necessary comments. (PreCond, PostCond, etc).

Hints & Notes

Keep in mind that the buffer contains a fixed number of frames which should be initialized and allocated at the start of the program. Any subsequent operations on the buffer should only involve modifying these frames without allocating any new ones.
Since the buffer manager manages a set of frames in memory which are mapped to pages on disk, a lookup mechanism is necessary for fast access (i.e. Hash Table). Make sure you encapsulate this mechanism in a separate class instead of merging it into your replacement policy class. This will make your life a lot easier when you switch the buffer manager to the other replacement policy.

Submission Procedure

How to hand in: You are a group of two students. Drop your project file, source code, executable, and documentation into one of your handin directories in \\goose\courses\cs432-fall01\handinA1. So if students with netids "abc1" and "xyz2" form a group together, one of the two handin directories (for example the directory \\goose\courses\cs432-fall01\handinA1\abc1) will contain the final project of the group. Make sure that the executable is ready to run, and that it can be recompiled as needed. Delete the handin folder of the other group member so that only one of your handin folders remains.

Keep a copy of the project in your own account just in case.

Grading Criteria

We will mark your programs based on the following criteria :

Correctness (65%)

You will get full marks if your implementation is correct. Partial credit will be given to a partially correct submission.

Coding Style (15%)

We expect you to write neat code. Code should be nicely indented and commented. We also expect you to follow the coding conventions.

Statistical Analysis (10%)

You should clearly describe what effects a larger buffer pool has on performance and why. You should use the statistics you collect to support your reasoning.

Documentation (10%)

You should also submit the online copy of your documentation using any format you like. (MS Word, HTML etc.), explaining the code that you have written. This should include assumptions that you made, description of any new class that you have added, and any other special feature we should take note of. As a guideline, the document should be 2-3 pages long (with normal fonts and spacing), or more if you feel necessary.

Collaboration

Project will be done in teams of two.

Both team members will receive the same grade. Also, collaboration across teams is not allowed, beyond discussing broad logical ideas (e.g. how does the clock algorithm work?) and C++ doubts (e.g.. how does one initialize static variables?). Looking at the code from another team is also not allowed. In any situation where a team feels that it may have compromised one of these guidelines or if you think that another team violates these guidelines, talk immediately to the instructors (or johannes@cs.cornell.edu).

Miscellaneous

Please let us know if there is any ambiguity in the assignment and please report any possible bugs as soon as possible by mailing a TA.

Other instructions and files

Click here for instructions on how to select a replacement policy.
Click here for instructions on how to set up your workspace and projects.
All the files are in the directory \\goose\courses\cs432-fall01\A1. You are welcome to develop at home or on a machine of your choice, but ultimately your code will be tested with the Visual C++ version in the undergraduate lab. So make sure that your code compiles and runs there.